#include<bits/stdc++.h>
#define N 10
#define INF 0x3f3f3f3f
using namespace std;

int M[N][N],D[N][N];
int path[N][N];
int m,n;

void Init()
{
	cout<<"m: ";cin>>m;
	cout<<"n: ";cin>>n;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
			D[i][j] = M[i][j] = (i == j ? 0 : INF), path[i][j] = j;
	}
	for(int i = 0; i < n; i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		M[u][v] = w;
	}
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
			cout<<M[i][j]<<(j == n-1?'\n':' ');
	}

	return ;
}

void Floyd()
{
	cout<<"Floyd start"<<endl;
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(D[i][k] + D[k][j] <  D[i][j])
					D[i][j] = D[i][k] + D[k][j], path[i][j] = path[i][k];
	cout<<"Floyd end"<<endl;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			printf("%d%c",D[i][j],j == n-1?'\n':' ');
		}
	}
	return ;
}





int main()
{
	Init();
	Floyd();


	while(1)
	{
		cout<<"u -> v";
		int u,v,f;
		cin>>u>>v;
		cout<<D[u][v];
		while(v!=u)
		{
			f = path[f][u];
		}


	}
	return 0;
}
